The invention concerns generally the field of decoding an encoded digital signal after transmission through a noisy transmission channel. Specifically the invention concerns the problem of estimating the correctness of a certain decoded sequence of digital symbols.
The widely known principle of convolutional encoding and its further developed forms like turbo encoding and concatenated convolutional encoding are commonly used for protecting a digital transmission against the detrimental error-introducing effects of a noisy transmission channel. Encoding is typically applied to discrete sequences of digital information, like frames or Protocol Data Units (PDUs). A receiver arranged to receive such an encoded transmitted sequence will apply a so-called Viterbi decoding algorithm to remove the encoding and to reconstruct the original digital sequence. As a background of the present invention we will briefly discuss some known features of Viterbi decoding.
A symbol sequence that has been constructed with a basically convolutional encoder of some kind will consist of a number of discrete symbols. Each symbol may be seen to represent k bits. Most practical implementations use binary convolutional encoding where the symbol length is one bit, although consecutive symbols may be grouped to form states. FIG. 1a illustrates a simple convolutional encoder that produces a xc2xd rate convolutional code. Input bits A(t) are fed from the left at the rate of one bit per unit time and two output bits X(t) and Y(t) per unit time are obtained at the right. The memory 101 of the convolutional encoder is represented as a shift register or an array of serially concatenated one bit memory cells (e.g. D-type flip-flops). The state of an encoder is represented as the contents of its memory, so the encoder of FIG. 1a a has the possible states 00, 01, 10 and 11. The length of the shift register determines the number of output bits in one output line to the values of which a single input bit has an influence: said number of output bits is known as the constraint length and in FIG. 1a it is three. An output bit may be calculated from an input bit and the known state of the encoder. For example in FIG. 1a, Y(t)=A(t)+A(txe2x88x921)+A(txe2x88x922) and the bit which at time t is known as A(t) will also influence the value of the output bits Y(t+1) and Y(t+2).
FIG. 1b illustrates a state matrix showing all possible states of the encoder of FIG. 1b at eight consecutive time instants. The correct sequence to be found through decoding corresponds to a path through the state matrix from left to right so that in each column the path goes through exactly one state. An exemplary path is shown in FIG. 1b as a continuous line. A graph showing states and paths through them is known as a trellis diagram and a path is also known as a trellis path.
It is a feature of the convolutional encoding and Viterbi decoding principle that from each known state there are only a certain number of allowed transitions to following states. A Viterbi decoder will find a number of possible paths through the trellis diagram by starting from a certain first state and propagating with allowed transitions from state to state. The observed transitions in the received, error-corrupted symbol sequence are seldom unequivocal but give rise to different interpretations with certain transition probabilities. The Viterbi decoder will use the information about the allowed state transitions and the observed transition probabilities to construct the possible trellis paths. In theory it would be possible to simulate every possible trellis path in the receiver and calculate its probability value in the light of the received sequence; however, the practical sequences are so long and the timing constraints are so tight that the exponentially growing number of possible paths would soon make the problem computationally impossibly complex. Practical Viterbi algorithms use certain reliability metrics to select at each state a single xe2x80x9csurvivingxe2x80x9d path or a limited number of xe2x80x9ccandidatexe2x80x9d paths to go on with. The path which provides the best estimated reliability in the log-likelihood sense at the final state will be declared to represent the decoded digital sequence.
In some cases the Viterbi algorithm will not be able to provide a single most probable path through the trellis diagram, or the most probable path still contains errors. Several approaches have been proposed for dealing with such a situation, one of them having been published in the article H. Yamamoto and K. Itoh: xe2x80x9cViterbi Decoding Algorithm for Convolutional Codes with Repeat Requestxe2x80x9d, IEEE Transactions on Information Theory, vol. IT-26, no.5, pp. 540-547, September. 1980, which is incorporated herein by reference. In the proposed method the surviving path for some i:th state is declared as unreliable if the metric difference between the two best paths to this state is smaller than a given threshold value or if the winning surviving path has at some previous time instant been declared as unreliable. If, at some time instant, the surviving paths to every state are declared as unreliable, the whole received sequence will be marked as unreliable and an erasure of information is declared. An advantage of the proposed method is that it requires only minimal overhead in processing or storage capacity when compared to straightforward Viterbi decoding. The article A. R. Raghavan and C. W. Baum: xe2x80x9cA Reliability Output Viterbi Algorithm with Applications to Hybrid ARQxe2x80x9d, IEEE Transactions on Information Theory, vol. IT-44, no.3, pp. 1214-1216, May. 1998, also incorporated herein by reference, proposes another approach in which a conditional a posteriori probability is calculated for errors in the decoded sequence. The theoretical performance of the latter approach is good but it requires a prohibitively complex calculational arrangement for practical applications in present-day communication devices.
A so-called list decoding or look-up decoding approach is also known in which the Viterbi decoding algorithm will not give a single output sequence with the highest log-likelihood value but a list of mutually alternative sequences in the order of diminishing likelihood values. A CRC (Cyclic Redundancy Check) checksum calculation or a similar other decoding method is then used to detect whether the n:th sequence in the list contains errors, starting with n=1. If there are errors in a certain sequence at place n in the list, the sequence at place n+1 is tried next until either an error-free sequence is found or all sequences in the list have been tried. Such an approach is known from e.g. the patent publication EP 0 606 724 A1 and the article Nill et al.: xe2x80x9cList and Soft Symbol Output Viterbi Algorithms: Extensions and Comparisonsxe2x80x9d, IEEE Transactions on Communications, Vol. 43, No. 2/3/4, February/March/April 1995. An advantage of the list decoding approach is that in many cases it saves time: making another xe2x80x9cguessxe2x80x9d of the correct form of the received sequence (in the form of taking another sequence from the list) and performing a CRC check is enormously faster than asking for and providing a retransmission from the transmitting device, so even if in some cases the whole list has to be exhausted and even then a restransmission must be requested, it suffices that for a significant number of times a retransmission can be avoided by actually finding the correct error-free sequence on the list.
A drawback of the list decoding principle is that it is quite memory-intensive: a number of mutually alternative sequences (and even the associated state-specific reliability values) must be temporarily stored in the receiving device, and only one of the stored sequences will ultimately be used. To reduce the amount of required storage capacity the patent publication WO 97/43834 proposes the concept of a decision window. A decision window is a structure containing a fixed number of columns from the trellis diagram. Initially the decision window is set so that at a certain symbol around the middle of the decision window all candidate paths will converge into a single state. It is a known characteristic of trellis paths that the nearest alternative (in the log-likelihood sense) to the sequence regarded as the most reliable one will diverge from it at a certain first time instant or column in the state matrix and converge again with it at a certain later time instant or column. The decision window -based list decoding method takes advantage of this known feature by constructing the alternative sequences by back-propagating from the common state of the decision window. Although the decision window concept helps to keep the memory requirements of list decoding in reasonable proportions, it is still quite complex and demanding in terms of computational capacity.
It is an object of the present invention to provide a method and a device for effectively estimating decoding reliability in a Viterbi-type decoding arrangement with low complexity in processing and hardware.
The objetcs of the invention are achieved by keeping track of the smallest metric difference between a surviving path and the best competing path throughout the span of the surviving path. Such tracking is separately made for each surviving path.
The method according to the invention is characterised in that it comprises the steps of
at a certain step of Viterbi decoding, updating a characteristic reliability metric separately in association with each selected surviving trellis path and
after selecting a final surviving trellis path, converting its characteristic reliability metric to a sequence reliability statistic corresponding to the estimated reliability of the decoded data sequence.
The invention also applies to a decoding apparatus, the characteristic feature of which is that it comprises means for updating, at each state associated with the intermediate or final time instants of Viterbi decoding, a characteristic reliability metric separately in association with each selected surviving trellis path and means for converting the characteristic reliability metric of the selected final surviving trellis path to a sequence reliability statistic corresponding to the estimated reliability of the decoded data sequence.
Additionally the invention applies to a receiving apparatus which is characterised in that it comprises
means for Viterbi decoding subunits by propagating a number of trellis paths from a number of allowed states associated with a certain initial time instant within a subunit to a number of allowed states associated with a certain final time instant within the same subunit through a number of allowed states associated with certain intermediate time instants, and by selecting, at each state associated with the intermediate time instants, a surviving trellis path and at the final time instant a final surviving trellis path,
means for updating, at each state associated with the intermediate or final time instants, a characteristic reliability metric separately in association with each selected surviving trellis path and means for converting the characteristic reliability metric of the selected final surviving trellis path to a sequence reliability statistic corresponding to the estimated reliability of the decoded data sequence, for estimating the decoding reliability of each subunit contained within a superunit,
error detection decoding means for error detection decoding a superunit and detecting the number of errors in it and
retransmission control means for identifying a predefined number of the subunits within the decoded superunit as suspicious on the basis of the estimated reliabilities of the subunits and the number of detected errors in the decoded superunit and for generating retransmission requests concerning the subunits identified as suspicious.
The invention exploits the known characteristic of Viterbi decoding that the reliability of a certain surviving path can be derived from the metric differences between the surviving path and the respective competing paths. In general, the closer a competing path gets in the sense of metric difference, the lower the reliability of the surviving path. According to the invention, a measure of the closest metric difference is established and maintained for each surviving path through the whole span of the path. After completing the Viterbi decoding the decoded sequences may be characterised by a sequence reliability statistic which is equal to or calculated from the maintained measures of closest metric difference.
An advantageous application where the calculated sequence reliability statistics may be used is one where a number of discretely decodable subsequences are covered by a single CRC checksum or similar error detection means that give an indication of a detected error without closer reference to the location of the error in the covered sequences. If the error detection means indicate that an error has occurred, the decoded subsequences may be arranged in an estimated reliability order according to their sequence reliability statistics. It is most probable that the error is located in the subsequence with the sequence reliability statistic indicating the weakest estimated reliability. If the transmission system allows for retransmissions on the subsequence level, the receiving device where the error has been detected may ask for the transmitting device to retransmit the most unreliable subsequence(s) and/or some additional information corresponding to it (or them) without the need to retransmit the whole CRC-protected group of subsequences.